package com.han.practice;

import java.util.Arrays;

/**
 * 美团模拟笔试-2
 * 求数组中3数的乘积最大值，且时间复杂度要求为O(n)，空间复杂度要求为O(1)
 */

public class MaxThreeNumberProduct {
    public static void main(String[] args) {


    }

    // todo 尚未考虑带有负数的情况
    public int maxProduct(int[] nums) {
        int[] factorArr = new int[3];
        for(int i=0; i<3; i++) factorArr[i] = nums[i];
        Arrays.sort(factorArr);

        for(int i=3; i<nums.length; i++){
            factorArr = rejusteFactorArr(factorArr, nums[i]);
        }
        return caculateProduct(factorArr);
    }

    public int[] rejusteFactorArr(int[] factorArr, int newNumber){
//        int[] rejustedFactorArr = new int[3];
        for(int i=0; i<factorArr.length; i++){
            if(factorArr[i] < newNumber){
                factorArr[i] = newNumber;
                break;
            }
        }

        Arrays.sort(factorArr);
        return factorArr;
    }

    public int caculateProduct(int[] factorArr){
        return factorArr[0]*factorArr[1]*factorArr[2];
    }
}
